import numpy as np
import heapq

class DijkstraPathFinder:
    def __init__(self, distances):
        self.distances = distances

    def run(self, start, end):
        # 使用 Dijkstra 算法计算从 start 到 end 的最短路径
        num_vertices = len(self.distances)
        visited = [False] * num_vertices
        min_distance = [float('inf')] * num_vertices
        min_distance[start] = 0
        previous_node = [-1] * num_vertices
        priority_queue = [(0, start)]

        while priority_queue:
            current_distance, current_vertex = heapq.heappop(priority_queue)

            if visited[current_vertex]:
                continue
            visited[current_vertex] = True

            if current_vertex == end:
                break

            for adjacent in range(num_vertices):
                if self.distances[current_vertex][adjacent] > 0 and not visited[adjacent]:
                    distance = current_distance + self.distances[current_vertex][adjacent]
                    if distance < min_distance[adjacent]:
                        min_distance[adjacent] = distance
                        previous_node[adjacent] = current_vertex
                        heapq.heappush(priority_queue, (distance, adjacent))

        return self.extract_path(previous_node, start, end)

    def extract_path(self, previous_node, start, end):
        path = []
        step = end
        while step != start:
            if step == -1:
                return []
            path.append(step)
            step = previous_node[step]
        path.append(start)
        path.reverse()
        return path

##############################################################################

# # 如需要在同一个文件中集成多个算法，可以在文件的底部添加测试和运行代码
# if __name__ == "__main__":
#     # 测试数据，定义一个距离矩阵
#     distances = np.array([
#         [0, 2, 0, 6, 0],
#         [2, 0, 3, 8, 5],
#         [0, 3, 0, 0, 7],
#         [6, 8, 0, 0, 9],
#         [0, 5, 7, 9, 0],
#     ])

#     # 创建 DijkstraPathFinder 实例并运行
#     dijkstra = DijkstraPathFinder(distances)
#     start_node = 0
#     end_node = 4
#     path = dijkstra.run(start_node, end_node)
#     print("Path from", start_node, "to", end_node, ":", path)
